﻿/*
 * [The "BSD license"]
 * Copyright (c) 2011 Terence Parr
 * All rights reserved.
 *
 * Conversion to C#:
 * Copyright (c) 2011 Sam Harwell, Pixel Mine, Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the author may not be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

namespace Antlr3.Analysis
{
    using StringBuilder = System.Text.StringBuilder;

    /** A tree node for tracking the call chains for NFAs that invoke
     *  other NFAs.  These trees only have to point upwards to their parents
     *  so we can walk back up the tree (i.e., pop stuff off the stack).  We
     *  never walk from stack down down through the children.
     *
     *  Each alt predicted in a decision has its own context tree,
     *  representing all possible return nodes.  The initial stack has
     *  EOF ("$") in it.  So, for m alternative productions, the lookahead
     *  DFA will have m NFAContext trees.
     *
     *  To "push" a new context, just do "new NFAContext(context-parent, state)"
     *  which will add itself to the parent.  The root is NFAContext(null, null).
     *
     *  The complete context for an NFA configuration is the set of invoking states
     *  on the path from this node thru the parent pointers to the root.
     */
    public class NFAContext : System.IEquatable<NFAContext>
    {
        /** This is similar to Bermudez's m constant in his LAR(m) where
         *  you bound the stack so your states don't explode.  The main difference
         *  is that I bound only recursion on the stack, not the simple stack size.
         *  This looser constraint will let the conversion roam further to find
         *  lookahead to resolve a decision.
         *
         *  Bermudez's m operates differently as it is his LR stack depth
         *  I'm pretty sure it therefore includes all stack symbols.  Here I
         *  restrict the size of an NFA configuration to be finite because a
         *  stack component may mention the same NFA invocation state at
         *  most m times.  Hence, the number of DFA states will not grow forever.
         *  With recursive rules like
         *
         *    e : '(' e ')' | INT ;
         *
         *  you could chase your tail forever if somebody said "s : e '.' | e ';' ;"
         *  This constant prevents new states from being created after a stack gets
         *  "too big".  Actually (12/14/2007) I realize that this example is
         *  trapped by the non-LL(*) detector for recursion in > 1 alt.  Here is
         *  an example that trips stack overflow:
         *
         *	  s : a Y | A A A A A X ; // force recursion past m=4
         *	  a : A a | Q;
         *
         *  If that were:
         *
         *	  s : a Y | A+ X ;
         *
         *  it could loop forever.
         *
         *  Imagine doing a depth-first search on the e DFA...as you chase an input
         *  sequence you can recurse to same rule such as e above.  You'd have a
         *  chain of ((((.  When you get do some point, you have to give up.  The
         *  states in the chain will have longer and longer NFA config stacks.
         *  Must limit size.
         *
         *  max=0 implies you cannot ever jump to another rule during closure.
         *  max=1 implies you can make as many calls as you want--you just
         *        can't ever visit a state that is on your rule invocation stack.
         * 		  I.e., you cannot ever recurse.
         *  max=2 implies you are able to recurse once (i.e., call a rule twice
         *  	  from the same place).
         *
         *  This tracks recursion to a rule specific to an invocation site!
         *  It does not detect multiple calls to a rule from different rule
         *  invocation states.  We are guaranteed to terminate because the
         *  stack can only grow as big as the number of NFA states * max.
         *
         *  I noticed that the Java grammar didn't work with max=1, but did with
         *  max=4.  Let's set to 4. Recursion is sometimes needed to resolve some
         *  fixed lookahead decisions.
         */
        public static int MAX_SAME_RULE_INVOCATIONS_PER_NFA_CONFIG_STACK = 4;

        private readonly NFAContext _parent;

        /** The NFA state that invoked another rule's start state is recorded
         *  on the rule invocation context stack.
         */
        private readonly NFAState _invokingState;

        /** Computing the hashCode is very expensive and closureBusy()
         *  uses it to track when it's seen a state|ctx before to avoid
         *  infinite loops.  As we add new contexts, record the hash code
         *  as this.invokingState + parent.cachedHashCode.  Avoids walking
         *  up the tree for every hashCode().  Note that this caching works
         *  because a context is a monotonically growing tree of context nodes
         *  and nothing on the stack is ever modified...ctx just grows
         *  or shrinks.
         */
        private readonly int _cachedHashCode;

        public NFAContext( NFAContext parent, NFAState invokingState )
        {
            this._parent = parent;
            this._invokingState = invokingState;
            if ( invokingState != null )
            {
                this._cachedHashCode = invokingState.StateNumber;
            }

            if ( parent != null )
            {
                this._cachedHashCode ^= (parent._cachedHashCode << 1) + (parent._cachedHashCode < 0 ? 1 : 0);
            }
        }

        public NFAContext Parent
        {
            get
            {
                return _parent;
            }
        }

        public NFAState InvokingState
        {
            get
            {
                return _invokingState;
            }
        }

        /** A context is empty if there is no parent; meaning nobody pushed
         *  anything on the call stack.
         */
        public bool IsEmpty
        {
            get
            {
                return _parent == null;
            }
        }

        /** Two contexts are equals() if both have
         *  same call stack; walk upwards to the root.
         *  Recall that the root sentinel node has no invokingStates and no parent.
         *  Note that you may be comparing contexts in different alt trees.
         *
         *  The hashCode is now cheap as it's computed once upon each context
         *  push on the stack.  Use it to make equals() more efficient.
         */
        public override bool Equals(object obj)
        {
            if (object.ReferenceEquals(this, obj))
                return true;

            NFAContext other = obj as NFAContext;
            if (other == null)
                return false;

            return this.Equals(other);
        }

        public bool Equals(NFAContext other)
        {
            if (object.ReferenceEquals(this, other))
                return true;

            if ( this._cachedHashCode != other._cachedHashCode )
            {
                return false; // can't be same if hash is different
            }

            if (_parent == null)
                return other._parent == null;

            return _parent.Equals(other._parent);
        }

        /** Two contexts conflict() if they are equals() or one is a stack suffix
         *  of the other.  For example, contexts [21 12 $] and [21 9 $] do not
         *  conflict, but [21 $] and [21 12 $] do conflict.  Note that I should
         *  probably not show the $ in this case.  There is a dummy node for each
         *  stack that just means empty; $ is a marker that's all.
         *
         *  This is used in relation to checking conflicts associated with a
         *  single NFA state's configurations within a single DFA state.
         *  If there are configurations s and t within a DFA state such that
         *  s.state=t.state && s.alt != t.alt && s.ctx conflicts t.ctx then
         *  the DFA state predicts more than a single alt--it's nondeterministic.
         *  Two contexts conflict if they are the same or if one is a suffix
         *  of the other.
         *
         *  When comparing contexts, if one context has a stack and the other
         *  does not then they should be considered the same context.  The only
         *  way for an NFA state p to have an empty context and a nonempty context
         *  is the case when closure falls off end of rule without a call stack
         *  and re-enters the rule with a context.  This resolves the issue I
         *  discussed with Sriram Srinivasan Feb 28, 2005 about not terminating
         *  fast enough upon nondeterminism.
         */
        public virtual bool ConflictsWith( NFAContext other )
        {
            return this.Suffix( other ); // || this.equals(other);
        }

        /** [$] suffix any context
         *  [21 $] suffix [21 12 $]
         *  [21 12 $] suffix [21 $]
         *  [21 18 $] suffix [21 18 12 9 $]
         *  [21 18 12 9 $] suffix [21 18 $]
         *  [21 12 $] not suffix [21 9 $]
         *
         *  Example "[21 $] suffix [21 12 $]" means: rule r invoked current rule
         *  from state 21.  Rule s invoked rule r from state 12 which then invoked
         *  current rule also via state 21.  While the context prior to state 21
         *  is different, the fact that both contexts emanate from state 21 implies
         *  that they are now going to track perfectly together.  Once they
         *  converged on state 21, there is no way they can separate.  In other
         *  words, the prior stack state is not consulted when computing where to
         *  go in the closure operation.  ?$ and ??$ are considered the same stack.
         *  If ? is popped off then $ and ?$ remain; they are now an empty and
         *  nonempty context comparison.  So, if one stack is a suffix of
         *  another, then it will still degenerate to the simple empty stack
         *  comparison case.
         */
        protected virtual bool Suffix( NFAContext other )
        {
            NFAContext sp = this;
            // if one of the contexts is empty, it never enters loop and returns true
            while ( sp._parent != null && other._parent != null )
            {
                if ( sp._invokingState != other._invokingState )
                {
                    return false;
                }
                sp = sp._parent;
                other = other._parent;
            }
            //JSystem.@out.println("suffix");
            return true;
        }

#if false
        /** Walk upwards to the root of the call stack context looking
         *  for a particular invoking state.
         */
        public virtual bool Contains( int state )
        {
            NFAContext sp = this;
            int n = 0; // track recursive invocations of state
            System.Console.Out.WriteLine( "this.context is " + sp );
            while ( sp.parent != null )
            {
                if ( sp.invokingState.stateNumber == state )
                {
                    return true;
                }
                sp = sp.parent;
            }
            return false;
        }
#endif

        /** Given an NFA state number, how many times has the NFA-to-DFA
         *  conversion pushed that state on the stack?  In other words,
         *  the NFA state must be a rule invocation state and this method
         *  tells you how many times you've been to this state.  If none,
         *  then you have not called the target rule from this state before
         *  (though another NFA state could have called that target rule).
         *  If n=1, then you've been to this state before during this
         *  DFA construction and are going to invoke that rule again.
         *
         *  Note that many NFA states can invoke rule r, but we ignore recursion
         *  unless you hit the same rule invocation state again.
         */
        public virtual int RecursionDepthEmanatingFromState( int state )
        {
            NFAContext sp = this;
            int n = 0; // track recursive invocations of target from this state
            //JSystem.@out.println("this.context is "+sp);
            while ( sp._parent != null )
            {
                if ( sp._invokingState.StateNumber == state )
                {
                    n++;
                }
                sp = sp._parent;
            }
            return n;
        }

        public override int GetHashCode()
        {
            return _cachedHashCode;
            /*
            int h = 0;
            NFAContext sp = this;
            while ( sp.parent!=null ) {
                h += sp.invokingState.getStateNumber();
                sp = sp.parent;
            }
            return h;
            */
        }

        public override string ToString()
        {
            StringBuilder buf = new StringBuilder();
            NFAContext sp = this;
            buf.Append( "[" );
            while ( sp._parent != null )
            {
                buf.Append( sp._invokingState.StateNumber );
                buf.Append( " " );
                sp = sp._parent;
            }
            buf.Append( "$]" );
            return buf.ToString();
        }
    }
}
